package nowcode;

import java.util.ArrayList;

public class MinKSolution {


    public static void main(String[] args) {
        int[] arr = new int[]{4, 5, 1, 6, 2, 7, 3, 8};
        MinKSolution solution = new MinKSolution();
        ArrayList<Integer> integers = solution.GetLeastNumbers_Solution(arr, 7);
        integers.forEach((i) -> {
            System.out.println(i);
        });
       /* solution.buildMapHead(arr);
        for (int i : arr) {
            System.out.println(i);
        }*/
    }

    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        if (input.length == 0 || k == 0 || k > input.length) {
            return result;
        }
        if (input.length == 1 && k == 1) {
            result.add(input[0]);
            return result;
        }
        int[] kHeap = new int[k];
        for (int i = 0; i < k; i++) {
            kHeap[i] = input[i];
        }
        buildMapHead(kHeap);
        for (int i = k; i < input.length; i++) {
            if (kHeap[0] > input[i]) {
                kHeap[0] = input[i];
                adjustMaxHeap(kHeap, 0);
            }
        }
        for (int i = 0; i < k; i++) {
            result.add(kHeap[i]);
        }

        return result;
    }


    private void buildMapHead(int[] kHeap) {
        if (kHeap.length == 1) {
            return;
        }
        for (int nodeIndex = ((kHeap.length - 1) / 2 - 1); nodeIndex >= 0; nodeIndex--) {
            adjustMaxHeap(kHeap, nodeIndex);
        }
    }

    private void adjustMaxHeap(int[] kHeap, int nodeIndex) {

        int leftChild = (nodeIndex + 1) * 2 - 1;
        int rightChild = (nodeIndex + 1) * 2;
        if (leftChild < kHeap.length && kHeap[leftChild] > kHeap[nodeIndex]) {
            int temp = kHeap[leftChild];
            kHeap[leftChild] = kHeap[nodeIndex];
            kHeap[nodeIndex] = temp;
            adjustMaxHeap(kHeap, leftChild);
        }
        if (rightChild < kHeap.length && kHeap[rightChild] > kHeap[nodeIndex]) {
            int temp = kHeap[rightChild];
            kHeap[rightChild] = kHeap[nodeIndex];
            kHeap[nodeIndex] = temp;
            adjustMaxHeap(kHeap, rightChild);
        }
    }


}
